package cn.cxq.learning.search;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class FibonacciSearch {

    private static List<Integer> getFibonacciArray(int high) {

        List<Integer> fibonacciArray = new ArrayList<>();

        fibonacciArray.add(1);
        fibonacciArray.add(1);

        while (high > fibonacciArray.get(fibonacciArray.size() - 1)) {
            fibonacciArray.add(fibonacciArray.get(fibonacciArray.size() - 1) + fibonacciArray.get(fibonacciArray.size() - 2));
        }

        return fibonacciArray;
    }

    public static int search(int[] arr, int value) {
        int low = 0;
        int high = arr.length - 1;

        List<Integer> fibonacciArray = getFibonacciArray(high);

        int[] temp = Arrays.copyOf(arr, fibonacciArray.get(fibonacciArray.size() - 1));

        for (int i = high + 1; i < temp.length; i++) temp[i] = arr[high];

        while (low < high) {
            int mid = low + fibonacciArray.get(fibonacciArray.size() - 2) - 1;
            if (value < temp[mid]) {
                high = mid - 1;
                fibonacciArray.remove(fibonacciArray.size() - 1);
            } else if (value > temp[mid]) {
                low = mid + 1;
                fibonacciArray.remove(fibonacciArray.size() - 1);
                fibonacciArray.remove(fibonacciArray.size() - 1);
            } else {
                if (high >= mid) return mid;
                else return high;
            }
        }
        return -1;
    }
}
